import java.util.Arrays;

public class Wu_97 {
    public static void main(String[] args) {
        double [] array = {2, 1, 3, 4, 7, 6, 5, 8, 8, 9, 5, 7, 8, 5, 4, 3};
        new Wu_97().quicksort(array, 0, array.length-1);
        System.out.println(Arrays.toString(array));
    }


    void quicksort(double [] array,int low,int high){
        if(low>=high) return;
        int i = low, j = high;
        //选base应避免选到极值，找三个值的中位数作为base
        double base = array[low];
        while(i<j){
        //必须先排右边,因为停止的位置要被换到开头，必须小于base
        // 这是因为外层循环到最后一次时
        //第一层循环结束的条件是 array[j]>=base 不成立
        //第二层循环结束的条件是 i<j 不成立（i=j）
        //这意味着停下来的时候，array[i]<base,此时swap,能满足我们要求选到的新base，左边全小于base，右边全大于base
        //那如果反过来，则意味着跳出外层循环的时候array[i]>base,此时这个要求就不能满足
            while(array[j]>=base && i<j){
                j--;
            }
            while(array[i]<=base && i<j){
                i++;
            }
            swap(array,i,j);
        }
        swap(array,low,j);
        quicksort(array,low,j-1);
        quicksort(array,j+1,high);
    }
    void swap(double [] array ,int i , int j){
        double key=array[i];
        array[i]=array[j];
        array[j]=key;
    }

}

